{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #游乐园的游览计划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #geometry #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #几何 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxWeight"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #游乐园的游览计划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>又到了一年一度的春游时间，小吴计划去游乐场游玩 1 天，游乐场总共有 <code>N</code> 个游乐项目，编号从 <code>0</code> 到 <code>N-1</code>。小吴给每个游乐项目定义了一个非负整数值 <code>value[i]</code> 表示自己的喜爱值。两个游乐项目之间会有双向路径相连，整个游乐场总共有 <code>M</code> 条双向路径，保存在二维数组&nbsp;<code>edges</code>中。 小吴计划选择一个游乐项目 <code>A</code> 作为这一天游玩的重点项目。上午小吴准备游玩重点项目 <code>A</code> 以及与项目 <code>A</code> 相邻的两个项目 <code>B</code>、<code>C</code> （项目<code>A</code>、<code>B</code>与<code>C</code>要求是不同的项目，且项目<code>B</code>与项目<code>C</code>要求相邻），并返回 <code>A</code> ，即存在一条 <code>A-B-C-A</code> 的路径。 下午，小吴决定再游玩重点项目 <code>A</code>以及与<code>A</code>相邻的两个项目 <code>B&#39;</code>、<code>C&#39;</code>，（项目<code>A</code>、<code>B&#39;</code>与<code>C&#39;</code>要求是不同的项目，且项目<code>B&#39;</code>与项目<code>C&#39;</code>要求相邻），并返回 <code>A</code> ，即存在一条 <code>A-B&#39;-C&#39;-A</code> 的路径。下午游玩项目 <code>B&#39;</code>、<code>C&#39;</code> 可与上午游玩项目<code>B</code>、<code>C</code>存在重复项目。 小吴希望提前安排好游玩路径，使得喜爱值之和最大。请你返回满足游玩路径选取条件的最大喜爱值之和，如果没有这样的路径，返回 <code>0</code>。 注意：一天中重复游玩同一个项目并不能重复增加喜爱值了。例如：上下午游玩路径分别是 <code>A-B-C-A</code>与<code>A-C-D-A</code> 那么只能获得 <code>value[A] + value[B] + value[C] + value[D]</code> 的总和。</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<blockquote>\n",
    "<p>输入：<code>edges = [[0,1],[1,2],[0,2]], value = [1,2,3]</code></p>\n",
    "\n",
    "<p>输出：<code>6</code></p>\n",
    "\n",
    "<p>解释：喜爱值之和最高的方案之一是 0-&gt;1-&gt;2-&gt;0 与 0-&gt;2-&gt;1-&gt;0 。重复游玩同一点不重复计入喜爱值，返回1+2+3=6</p>\n",
    "</blockquote>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<blockquote>\n",
    "<p>输入：<code>edges = [[0,2],[2,1]], value = [1,2,5]</code></p>\n",
    "\n",
    "<p>输出：<code>0</code></p>\n",
    "\n",
    "<p>解释：无满足要求的游玩路径，返回 0</p>\n",
    "</blockquote>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<blockquote>\n",
    "<p>输入：<code>edges = [[0,1],[0,2],[0,3],[0,4],[0,5],[1,3],[2,4],[2,5],[3,4],[3,5],[4,5]], value = [7,8,6,8,9,7]</code></p>\n",
    "\n",
    "<p>输出：<code>39</code></p>\n",
    "\n",
    "<p>解释：喜爱值之和最高的方案之一是 3-&gt;0-&gt;1-&gt;3 与 3-&gt;4-&gt;5-&gt;3 。喜爱值最高为 7+8+8+9+7=39</p>\n",
    "</blockquote>\n",
    "\n",
    "<p><strong>限制：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= value.length &lt;= 10000</code></li>\n",
    "\t<li><code>1 &lt;=&nbsp;edges.length &lt;= 10000</code></li>\n",
    "\t<li><code>0 &lt;= edges[i][0],edges[i][1] &lt;&nbsp;value.length</code></li>\n",
    "\t<li><code>0 &lt;= value[i] &lt;= 10000</code></li>\n",
    "\t<li><code>edges中没有重复的边</code></li>\n",
    "\t<li><code>edges[i][0] != edges[i][1]</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [you-le-yuan-de-you-lan-ji-hua](https://leetcode.cn/problems/you-le-yuan-de-you-lan-ji-hua/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [you-le-yuan-de-you-lan-ji-hua](https://leetcode.cn/problems/you-le-yuan-de-you-lan-ji-hua/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1],[1,2],[0,2]]\\n[1,2,3]', '[[0,2],[2,1]]\\n[1,2,5]', '[[0,1],[0,2],[0,3],[0,4],[0,5],[1,3],[2,4],[2,5],[3,4],[3,5],[4,5]]\\n[7,8,6,8,9,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWeight(self, edges: List[List[int]], value: List[int]) -> int:\n",
    "        d=defaultdict(set)\n",
    "        for a,b in edges:\n",
    "            d[a].add(b)\n",
    "            d[b].add(a)\n",
    "        res=0\n",
    "        for i in range(len(value)):\n",
    "            triangles=[[a,b] for a,b in edges if a in d[i] and b in d[i]] if len(d[i])**2>=len(edges) \\\n",
    "                else [[a,b] for a in d[i] for b in d[i] if a in d[b]]\n",
    "            candidates=sorted([value[a]+value[b],[a,b]] for a,b in triangles)\n",
    "            res=max(res,(value[i]+candidates[0][0]) if candidates else 0) # 只有0或1个元素时\n",
    "            for v1,nodes1 in candidates[-3:]:\n",
    "                for v2,nodes2 in candidates:\n",
    "                    if v1==v2:\n",
    "                        continue\n",
    "                    v=value[i]+v1+v2-sum(value[node] for node in set(nodes1) & set(nodes2))\n",
    "                    res=max(res,v)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxWeight(self, e: List[List[int]], v: List[int]) -> int:\n",
    "        n = len(v)\n",
    "        se = []\n",
    "        deg = [0] * n\n",
    "        has = [defaultdict(bool) for _ in range(n)]\n",
    "\n",
    "        for i in e:\n",
    "            se.append((-v[i[0]] - v[i[1]], (i[0], i[1])))\n",
    "            has[i[0]][i[1]] = has[i[1]][i[0]] = True\n",
    "            deg[i[0]] += 1\n",
    "            deg[i[1]] += 1\n",
    "\n",
    "        se.sort()\n",
    "\n",
    "        def t(a, b, c, d):\n",
    "            ret = v[a] + v[b]\n",
    "            if c != a and c != b:\n",
    "                ret += v[c]\n",
    "            if d != a and d != b:\n",
    "                ret += v[d]\n",
    "            return ret\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if deg[i] >= 100:\n",
    "                a1 = b1 = a2 = b2 = a3 = b3 = -1\n",
    "                nowres = 0\n",
    "                for j in se:\n",
    "                    a, b = j[1]\n",
    "                    if a in has[i] and b in has[i]:\n",
    "                        if a1 == -1:\n",
    "                            a1, b1 = a, b\n",
    "                            nowres = v[a] + v[b]\n",
    "                        elif a2 == -1:\n",
    "                            a2, b2 = a, b\n",
    "                            nowres = t(a1, b1, a, b)\n",
    "                        elif a3 == -1:\n",
    "                            a3, b3 = a, b\n",
    "                            nowres = max(nowres, t(a1, b1, a, b))\n",
    "                            nowres = max(nowres, t(a2, b2, a, b))\n",
    "                        else:\n",
    "                            nowres = max(nowres, t(a1, b1, a, b))\n",
    "                            nowres = max(nowres, t(a2, b2, a, b))\n",
    "                            nowres = max(nowres, t(a3, b3, a, b))\n",
    "\n",
    "                if a1 != -1:\n",
    "                    ans = max(ans, nowres + v[i])\n",
    "            else:\n",
    "                nnn = []\n",
    "                eds = []\n",
    "\n",
    "                for j in has[i]:\n",
    "                    nnn.append(j)\n",
    "\n",
    "                for a in nnn:\n",
    "                    for b in nnn:\n",
    "                        if a < b and b in has[a]:\n",
    "                            eds.append((-v[a] - v[b], (a, b)))\n",
    "\n",
    "                eds.sort()\n",
    "\n",
    "                a1 = b1 = a2 = b2 = a3 = b3 = -1\n",
    "                nowres = 0\n",
    "\n",
    "                for j in eds:\n",
    "                    a, b = j[1]\n",
    "                    if a1 == -1:\n",
    "                        a1, b1 = a, b\n",
    "                        nowres = v[a] + v[b]\n",
    "                    elif a2 == -1:\n",
    "                        a2, b2 = a, b\n",
    "                        nowres = t(a1, b1, a, b)\n",
    "                    elif a3 == -1:\n",
    "                        a3, b3 = a, b\n",
    "                        nowres = max(nowres, t(a1, b1, a, b))\n",
    "                        nowres = max(nowres, t(a2, b2, a, b))\n",
    "                    else:\n",
    "                        nowres = max(nowres, t(a1, b1, a, b))\n",
    "                        nowres = max(nowres, t(a2, b2, a, b))\n",
    "                        nowres = max(nowres, t(a3, b3, a, b))\n",
    "\n",
    "                if a1 != -1:\n",
    "                    ans = max(ans, nowres + v[i])\n",
    "\n",
    "        return ans\n",
    "\n",
    "# Test cases\n",
    "sol = Solution()\n",
    "print(sol.maxWeight([[0, 1], [1, 2], [2, 3]], [1, 2, 3, 4]))  # Output should be based on your expected output\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef maxWeight(self, edges, value):\n",
    "\t\tn = len(value)\n",
    "\t\tmap0 = [set() for _ in range(n)]\n",
    "\t\tgr = [set() for _ in range(n)]\n",
    "\t\tsm = [set() for _ in range(n)]\n",
    "\t\tfor u, v in edges:\n",
    "\t\t\tmap0[u].add(v)\n",
    "\t\t\tmap0[v].add(u)\n",
    "\t\t\tgr[min(u, v)].add(max(u, v))\n",
    "\t\t\tsm[max(u, v)].add(min(u, v))\n",
    "\t\tans = 0\n",
    "\t\tvalue.append(float('-inf')) #调用函数未找到合法值返回序号-1\n",
    "\t\tfor u, v in edges:\n",
    "\t\t\tx1, x2 = self.find(map0[u] & map0[v], value)\n",
    "\t\t\tans = max(ans, value[u] + value[v] + value[x1] + max(0, value[x2])) #3个或4个点\n",
    "\t\tfor u in range(n):\n",
    "\t\t\tans = max(ans, self.calc(u, [x for x in map0[u] if len(map0[x]) >= 2], map0, sm, value))\n",
    "\t\treturn ans\n",
    "\t\n",
    "\t#动态规划5点路线, 遍历arr(已升序排列)下标i, 上午游览<arr[i]的两个点, 下午游览arr[i]与一个小于arr[i]的点\n",
    "\tdef calc(self, mid, arr, map0, sm, value):\n",
    "\t\tn = len(arr)\n",
    "\t\tif n < 4:\n",
    "\t\t\treturn 0\n",
    "\t\tloc = {x: i for i, x in enumerate(arr)}\n",
    "\t\tres = 0\n",
    "\t\tvalid = set(arr)\n",
    "\t\tlast = [float('-inf')] * n #截至当前遍历位置, 不含arr[i]的路线mid-x-y最大value(不含mid)\n",
    "\t\tq = [[float('-inf'), i] for i in range(n)]\n",
    "\t\tfor i, u in enumerate(arr): #只使用<i位置的点\n",
    "\t\t\tupdate = {} #外层循环完成一轮后才更新last\n",
    "\t\t\tfor v in sm[u] & valid:\n",
    "\t\t\t\tif mid in map0[v]:\n",
    "\t\t\t\t\tval = value[u] + value[v]\n",
    "\t\t\t\t\tres = max(res, value[mid] + val + last[loc[v]])\n",
    "\t\t\t\t\tdup = [] #含u, v的位置, 及时有更大值也不更新\n",
    "\t\t\t\t\twhile q and q[0][0] < val:\n",
    "\t\t\t\t\t\ttmp = heapq.heappop(q)\n",
    "\t\t\t\t\t\tif tmp[1] in {i, loc[v]}:\n",
    "\t\t\t\t\t\t\tdup.append(tmp)\n",
    "\t\t\t\t\t\telse:\n",
    "\t\t\t\t\t\t\theapq.heappush(q, [val, tmp[1]])\n",
    "\t\t\t\t\t\t\tupdate[tmp[1]] = val\n",
    "\t\t\t\t\tfor t in dup:\n",
    "\t\t\t\t\t\theapq.heappush(q, t)\n",
    "\t\t\tfor key in update:\n",
    "\t\t\t\tlast[key] = update[key]\n",
    "\t\treturn res\n",
    "\t\n",
    "\tdef find(self, pool, value):\n",
    "\t\tres = [-1,-1]\n",
    "\t\tfor x in pool:\n",
    "\t\t\tif value[x] > value[res[0]]:\n",
    "\t\t\t\tres[1] = res[0]\n",
    "\t\t\t\tres[0] = x\n",
    "\t\t\telif value[x] > value[res[1]]:\n",
    "\t\t\t\tres[1] = x\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWeight(self, edges: List[List[int]], value: List[int]) -> int:\n",
    "        M,N = len(edges),len(value) # M:边的数量，N:点的数量\n",
    "\n",
    "        # 对边按权值和排序，以便之后对每个点，直接获得按权值和排序的边\n",
    "        edges.sort(key=lambda e:-(value[e[0]]+value[e[1]]))\n",
    "        # print('edges',edges)\n",
    "\n",
    "        # 统计各个点的度数（出边数量）\n",
    "        cnts = [0]*N\n",
    "        for v in edges:\n",
    "            cnts[v[0]]+=1\n",
    "            cnts[v[1]]+=1\n",
    "        # print('cnts',cnts)\n",
    "\n",
    "        # 将无向图重建为有向图（度小->度大）\n",
    "        G = [[] for _ in range(N)]\n",
    "        for e_id, (left_id, right_id) in enumerate(edges):\n",
    "            if cnts[left_id] < cnts[right_id] or (cnts[left_id] == cnts[right_id] and left_id<right_id):\n",
    "                G[left_id].append([right_id, e_id])\n",
    "            else:\n",
    "                G[right_id].append([left_id, e_id])\n",
    "        # print('print g')\n",
    "\n",
    "        # # 求所有的三元环，并按边归类\n",
    "        nodes,vis,idxs = [[] for _ in range(M)],[-1]*N,[0]*N\n",
    "        for e_id, (a_id, b_id) in enumerate(edges):\n",
    "            for next_id,next_e_id in G[a_id]:\n",
    "                vis[next_id] = e_id\n",
    "                idxs[next_id] = next_e_id\n",
    "            for next_id,next_e_id in G[b_id]:\n",
    "                if vis[next_id] == e_id:    # 形成回路\n",
    "                    nodes[next_e_id].append(a_id)\n",
    "                    nodes[idxs[next_id]].append(b_id)\n",
    "                    nodes[e_id].append(next_id)\n",
    "        # print('nodes',nodes)\n",
    "\n",
    "        # 将三元环按顶点归类，每个顶点自动获得按权值和排序的边\n",
    "        centers = [[] for _ in range(N)]\n",
    "        for i in range(M):\n",
    "            for n in nodes[i]:\n",
    "                centers[n].append(i)\n",
    "        # print('centers',centers)\n",
    "\n",
    "        # 求出结果\n",
    "        res = 0\n",
    "        for c_id,nexts in enumerate(centers):\n",
    "            len_next = len(nexts)\n",
    "            bound = len_next-1\n",
    "            for e_a_id,e_a in enumerate(nexts):\n",
    "                if e_a_id>min(3,bound):break\n",
    "                cur_0 = value[c_id] + value[edges[e_a][0]] + value[edges[e_a][1]] # 边a的两端（第一个三角形）\n",
    "                for e_b_id in range(e_a_id, len_next):\n",
    "                    cur = cur_0\n",
    "                    cnt = 0\n",
    "                    if edges[nexts[e_b_id]][0] not in edges[e_a]:   # b的一端（第二个三角形的一个点）\n",
    "                        cur += value[edges[nexts[e_b_id]][0]]\n",
    "                        cnt += 1\n",
    "                    if edges[nexts[e_b_id]][1] not in edges[e_a]:   # b的另一端（第二个三角形的另一个点）\n",
    "                        cur += value[edges[nexts[e_b_id]][1]]\n",
    "                        cnt += 1\n",
    "                    # print(f\"c_id:{c_id}, c:{nexts}, a:{e_a_id}, b:{e_b_id}, cnt:{cnt}, cur:{cur}, res:{res}\")\n",
    "                    res = max(res, cur)\n",
    "                    if cnt==2: # 从大到小，如果找到两个三角形了，则找到两个三角形的边界情况\n",
    "                        bound = e_b_id-1\n",
    "                        break\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "暴力枚举所有可能的三角形\n",
    "'''\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedSet\n",
    "\n",
    "class Solution:\n",
    "    def maxWeight(self, edges: List[List[int]], value: List[int]) -> int:\n",
    "        link = {}\n",
    "        for a, b in edges:\n",
    "            if a not in link:\n",
    "                link[a] = SortedSet()\n",
    "            if b not in link:\n",
    "                link[b] = SortedSet()\n",
    "\n",
    "            link[a].add(b)\n",
    "            link[b].add(a)\n",
    "\n",
    "        ans = 0\n",
    "        for node in link.keys():\n",
    "            next = list(link[node])\n",
    "            pairs = []\n",
    "\n",
    "            # 枚举另外两个节点组成的pair对\n",
    "            if len(next) < 50:\n",
    "                # 度比较小的点枚举和node直连的点\n",
    "                for i in range(len(next)):\n",
    "                    for j in range(i+1, len(next)):\n",
    "                        node1, node2 = next[i], next[j]\n",
    "                        if node1 in link and node2 in link[node1]:\n",
    "                            pairs.append((node1, node2))\n",
    "            else:\n",
    "                # 度比较大的点枚举边\n",
    "                for node1, node2 in edges:\n",
    "                    if node1 in link[node] and node2 in link[node]:\n",
    "                        pairs.append((node1, node2))\n",
    "\n",
    "            if len(pairs) == 0:\n",
    "                continue\n",
    "\n",
    "            # 找最大的三角形\n",
    "            max_val = -1\n",
    "            max_node_sets = set()\n",
    "            max_pairs = set()\n",
    "            for a, b in pairs:\n",
    "                if max_val < value[a] + value[b]:\n",
    "                    max_val = value[a] + value[b]\n",
    "                    max_node_sets = {a, b}\n",
    "                    max_pairs = {(a, b)}\n",
    "                elif max_val ==  value[a] + value[b]:\n",
    "                    max_node_sets.add(a)\n",
    "                    max_node_sets.add(b)\n",
    "                    max_pairs.add((a, b))\n",
    "\n",
    "            # 最大三角形的pair对中的两个点分散在两个三角形中的情况\n",
    "            possible_pairs = [pair for pair in pairs if pair[0] in max_node_sets or pair[1] in max_node_sets]\n",
    "            for i in range(len(possible_pairs)):\n",
    "                for j in range(i, len(possible_pairs)):\n",
    "                    total = 0\n",
    "                    for other_node in set([possible_pairs[i][0], possible_pairs[i][1], possible_pairs[j][0], possible_pairs[j][1]]):\n",
    "                        total += value[other_node]\n",
    "                    ans = max(ans, total + value[node])\n",
    "\n",
    "            # 最大三角形的pair中两个点在一个三角形中的情况\n",
    "            for max_a, max_b in max_pairs:\n",
    "                for a, b in pairs:\n",
    "                    total = 0\n",
    "                    for other_node in set([a, b, max_a, max_b]):\n",
    "                        total += value[other_node]\n",
    "                    ans = max(ans, total + value[node])\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def get_top3(self, triangle_lst, triangle_info):\n",
    "        # 更新同一条边的 top3 的三角形\n",
    "        if not triangle_lst:\n",
    "            return [triangle_info]\n",
    "        if triangle_lst[-1][-1] >= triangle_info[-1]:\n",
    "            triangle_lst.append(triangle_info)\n",
    "            return triangle_lst\n",
    "        for index, _ in enumerate(triangle_lst):\n",
    "            if triangle_lst[index][-1] < triangle_info[-1]:\n",
    "                triangle_lst.insert(index, triangle_info)\n",
    "                break\n",
    "        triangle_lst = triangle_lst[:3]\n",
    "        return triangle_lst\n",
    "\n",
    "    def maxWeight(self, edges: List[List[int]], value: List[int]) -> int:\n",
    "        n = len(value)\n",
    "        self.value = value\n",
    "        # 生成邻接表,记录与point点相连且编号大于point的所有点\n",
    "        point_set = collections.defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            if x > y:\n",
    "                x, y = y, x\n",
    "            point_set[x].add(y)\n",
    "\n",
    "        max_triangle_point_dict = collections.defaultdict(list)\n",
    "        triangle_point_dict = collections.defaultdict(list)\n",
    "        # 边（i,j）能构成的 Top3 三角形\n",
    "        triangle_edge_dict = collections.defaultdict(list)\n",
    "\n",
    "        for i in range(0, n):\n",
    "            for j in point_set[i]:\n",
    "                # 能与 i,j 构成三角形的点\n",
    "                all_points_lst = list(point_set[i] & point_set[j])\n",
    "                for k in all_points_lst:\n",
    "                    # 满足 i < j < k\n",
    "                    sum_value = value[i] + value[j] + value[k]\n",
    "                    triangle_info = [i, j, k, sum_value]\n",
    "                    # i,j,k 三个点  记录和更新三角形信息\n",
    "                    for lm in [i, j, k]:\n",
    "                        if not max_triangle_point_dict[lm] or max_triangle_point_dict[lm][-1] < sum_value:\n",
    "                            max_triangle_point_dict[lm] = triangle_info\n",
    "                        triangle_point_dict[lm].append(triangle_info)\n",
    "                    # 三个边 记录和更新三角形信息\n",
    "                    for edge in [(i, j), (i, k), (j, k)]:\n",
    "                        triangle_edge_dict[edge] = self.get_top3(triangle_edge_dict[edge], triangle_info)\n",
    "        res = 0\n",
    "        for i in range(0, n):\n",
    "            # 点无三角形的情况\n",
    "            if not max_triangle_point_dict[i]:\n",
    "                continue\n",
    "            max_triangle = max_triangle_point_dict[i]\n",
    "            # 两个三角形完全重合的情况，即一个三角形\n",
    "            res = max(res, max_triangle[-1])\n",
    "\n",
    "            # 最大三角形 max_triangle 和所有包含 i 的三角形 一一组合\n",
    "            for info in triangle_point_dict[i]:\n",
    "                res = max(res, self.count_val(max_triangle, info))\n",
    "\n",
    "            # 两个包含 max_triangle 边（i,x) （i,y)的Top3三角形一一组合\n",
    "            max_points = max_triangle[:3]\n",
    "            max_points.remove(i)\n",
    "            edge1, edge2 = [(i, x) if i < x else (x, i) for x in max_points]\n",
    "            for info1 in triangle_edge_dict[edge1]:\n",
    "                for info2 in triangle_edge_dict[edge2]:\n",
    "                    res = max(res, self.count_val(info1, info2))\n",
    "        return res\n",
    "\n",
    "    def count_val(self, info1, info2):\n",
    "        # 计算两个三角的val总和，过滤重复点\n",
    "        all_points = set(info1[:3]) | set(info2[:3])\n",
    "        return sum(self.value[x] for x in all_points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWeight(self, edges: List[List[int]], value: List[int]) -> int:\n",
    "        N = len(value)\n",
    "        le = [set() for _ in range(N)]\n",
    "\n",
    "        for a, b in edges:\n",
    "            le[a].add(b)\n",
    "            le[b].add(a)\n",
    "\n",
    "        # 返回值分两种情况\n",
    "        ret = 0\n",
    "\n",
    "        # 上午下午有两个重复，记录第三个点的第一和第二最大\n",
    "        dab = defaultdict(lambda: [0, 0, -1, -1])\n",
    "\n",
    "        def calc_ab(vab, vc, c, l):\n",
    "            nonlocal ret\n",
    "\n",
    "            if vc >= l[0]:\n",
    "                ret = max(ret, vab + vc + l[0])\n",
    "                l[0], l[1], l[2], l[3] = vc, l[0], c, l[2]\n",
    "            elif vc >= l[1]:\n",
    "                ret = max(ret, vab + vc + l[0])\n",
    "                l[1], l[3] = vc, c\n",
    "\n",
    "        # 上午下午没有重复\n",
    "        da = defaultdict(list)\n",
    "\n",
    "        for a, s in enumerate(le):\n",
    "            va = value[a]\n",
    "\n",
    "            for b in s:\n",
    "                if b < a:\n",
    "                    continue\n",
    "\n",
    "                vb = value[b]\n",
    "\n",
    "                for c in le[b]:\n",
    "                    if c < b or c not in s:\n",
    "                        continue\n",
    "\n",
    "                    vc = value[c]\n",
    "\n",
    "                    l = dab[a, b]\n",
    "                    calc_ab(va + vb, vc, c, l)\n",
    "                    l = dab[b, c]\n",
    "                    calc_ab(vb + vc, va, a, l)\n",
    "                    l = dab[a, c]\n",
    "                    calc_ab(va + vc, vb, b, l)\n",
    "\n",
    "                    v = va + vb + vc\n",
    "                    da[a].append((v, b, c))\n",
    "                    da[b].append((v, a, c))\n",
    "                    da[c].append((v, a, b))\n",
    "\n",
    "        def calc_a1(v, a, b, c, l):\n",
    "            nonlocal ret\n",
    "\n",
    "            for _v, _b, _c in l:\n",
    "                if b != _b and b != _c and c != _b and c != _c:\n",
    "                    ret = max(ret, v + _v - value[a])\n",
    "\n",
    "        def calc_a2(a, b, c, l):\n",
    "            nonlocal ret\n",
    "\n",
    "            # 找到ab对应的第二大点，第一大点为c\n",
    "            lab = dab[a, b] if a < b else dab[b, a]\n",
    "\n",
    "            if lab[3] == -1:\n",
    "                # ab只有一个c对应\n",
    "                return\n",
    "\n",
    "            if lab[3] == c:\n",
    "                _c = lab[2]\n",
    "            else:\n",
    "                _c = lab[3]\n",
    "\n",
    "            # 使用ab_c\n",
    "            v = value[a] + value[b] + value[_c]\n",
    "            calc_a1(v, a, b, _c, l)\n",
    "\n",
    "            if _c not in le[c]:\n",
    "                # _c 不能和c配套，肯定和b配对\n",
    "                return\n",
    "\n",
    "            # 使用ac_c\n",
    "            v = value[a] + value[c] + value[_c]\n",
    "            calc_a1(v, a, c, _c, l)\n",
    "\n",
    "        for a, l in da.items():\n",
    "            # 找到最大值\n",
    "            maxv = 0\n",
    "\n",
    "            for v, b, c in l:\n",
    "                if v > maxv:\n",
    "                    maxv, maxb, maxc = v, b, c\n",
    "\n",
    "            # 分两种情况\n",
    "            # 使用最大的\n",
    "            calc_a1(maxv, a, maxb, maxc, l)\n",
    "\n",
    "            # 不使用最大的，那就说明肯定分别使用了ab和ac\n",
    "            calc_a2(a, maxb, maxc, l)\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxWeight(self, edges: List[List[int]], value: List[int]) -> int:\n",
    "        n = len(value)\n",
    "        neighbors = [set() for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            neighbors[i].add(j)\n",
    "            neighbors[j].add(i)\n",
    "        circles = [[] for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in neighbors[i]:\n",
    "                for k in neighbors[i]:\n",
    "                    if j >= k: continue\n",
    "                    if k in neighbors[j]:\n",
    "                        circles[i].append((value[j] + value[k], j, k))\n",
    "            circles[i].sort()\n",
    "            for j in range(min(len(circles[i]), 3)):\n",
    "                s = set()\n",
    "                s.add(circles[i][-1 - j][1])\n",
    "                s.add(circles[i][-1 - j][2])\n",
    "                ans = max(ans, value[i] + circles[i][-1 - j][0])\n",
    "                for k in range(j + 1, len(circles[i])):\n",
    "                    tmp = circles[i][-1 - j][0]\n",
    "                    if circles[i][-1 - k][1] not in s:\n",
    "                        tmp += value[circles[i][-1 - k][1]]\n",
    "                    if circles[i][-1 - k][2] not in s:\n",
    "                        tmp += value[circles[i][-1 - k][2]]\n",
    "                    ans = max(ans, value[i] + tmp)\n",
    "                    if circles[i][-1 - k][1] not in s and circles[i][-1 - k][2] not in s:\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def maxWeight(self, edges: List[List[int]], weight: List[int]) -> int:\n",
    "        n = len(weight)\n",
    "        self.weight = weight\n",
    "        point_set = collections.defaultdict(set) # 记录和 i相连且编号大于i的所有点\n",
    "        for x,y in edges:\n",
    "            if x>y:\n",
    "                x,y = y,x\n",
    "            point_set[x].add(y)\n",
    "\n",
    "        max_triangle_point_dict = collections.defaultdict(list)  # 点i能构成的最大三角形\n",
    "        triangle_point_dict = collections.defaultdict(list) # 点i能构成的所有三角形\n",
    "        triangle_edge_dict = collections.defaultdict(list)  # 边(i,j)能构成的 Top3 三角形\n",
    "\n",
    "        # 查找三角形\n",
    "        for i in range(0,n):\n",
    "            for j in point_set[i]:\n",
    "                all_points_list = list(point_set[i]&point_set[j]) # 能与 i,j 构成三角形的点\n",
    "                for k in all_points_list:\n",
    "                    # 由于 point_set 结构， 满足 i<j<k\n",
    "                    sum_weight = weight[i]+weight[j]+weight[k]\n",
    "                    triangle_info = [i,j,k,sum_weight]\n",
    "                    # i,j,k 三个点 记录和更新三角形信息\n",
    "                    for lm in [i,j,k]:\n",
    "                        if not max_triangle_point_dict[lm] or max_triangle_point_dict[lm][-1]<sum_weight:\n",
    "                            max_triangle_point_dict[lm] = triangle_info\n",
    "                        triangle_point_dict[lm].append([i,j,k])\n",
    "                    # 三个条边 记录和更新三角形信息\n",
    "                    for edge in [(i,j),(i,k),(j,k)]:\n",
    "                        triangle_edge_dict[edge] = self.get_top3(triangle_edge_dict[edge],triangle_info)\n",
    " \n",
    "        res = 0\n",
    "        for i in range(0,n):\n",
    "            # 点无三角形的情况\n",
    "            if not max_triangle_point_dict[i]:\n",
    "                continue\n",
    "            max_triange = max_triangle_point_dict[i]\n",
    "            # 两个三角形完全重合的情况，即一个三角形\n",
    "            res = max(res,max_triange[-1])\n",
    "\n",
    "            # 最大三角形 max_triange 和所有包含 i 的三角形一一组合\n",
    "            for info in triangle_point_dict[i]:\n",
    "                res = max(res,self.count_val(max_triange,info))\n",
    "        \n",
    "            # 两个包含max_triangle边（i,x),(i,y) 的 Top3 三角形一一组合\n",
    "            max_points = max_triange[:3]\n",
    "            max_points.remove(i)\n",
    "            edge1,edge2 = [(i,x) if i<x else (x,i) for x in max_points]\n",
    "            for info1 in triangle_edge_dict[edge1]:\n",
    "                for info2 in triangle_edge_dict[edge2]:\n",
    "                    res = max(res,self.count_val(info1,info2))\n",
    "        \n",
    "        return res\n",
    "    \n",
    "    def count_val(self, info1, info2):\n",
    "        # 计算 两个三角的val总和， 过滤重复点\n",
    "        all_points = set(info1[:3])|set(info2[:3])\n",
    "        return sum([self.weight[x] for x in all_points])\n",
    "        \n",
    "    def get_top3(self, triangle_list, triangle_info):\n",
    "        # 更新 同一条边 的 top3 的三角形\n",
    "        if not triangle_list:\n",
    "            return [triangle_info]\n",
    "        if triangle_list[-1][-1]>=triangle_info[-1]:\n",
    "            triangle_list.append(triangle_info)\n",
    "            return triangle_list\n",
    "        for index in range(0,len(triangle_list)):\n",
    "            if triangle_list[index][-1]<triangle_info[-1]:\n",
    "                triangle_list.insert(index,triangle_info)\n",
    "                break\n",
    "        triangle_list = triangle_list[:3]\n",
    "        return triangle_list\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
